Leonardo the Inventor/Leonardo The Inventor (93026)(Broderbund)(Riverdeep)(2004).iso/LEOWINMV/SHARED.DIR/03072_Script_BINARY SEARCH

Text File | 1996-04-01 | 2KB | 58 lines

-- -----------------------------------------------------------
-- Handler binSearchFirstItemInLine performs a binary search
-- searching for the line in given source containing the given
-- target. the source has the given delimiter.

on BinSearchFirstItemInLine source, target, delimiter
  -- Source must be sorted, and have a blank line at the end.

  if (length(source) = 0) or (length(target) = 0) then return 0

  set oldDelimiter = the itemDelimiter

  if not(voidP(delimiter)) then
    set the itemDelimiter = delimiter
  end if

  set RangeBegin = 1
  set RangeEnd = the number of lines of source
  set CurrentLine = RangeBegin + integer ((RangeEnd - RangeBegin) / 2)

  set found = FALSE

  repeat while found = FALSE
    set maybeTarget = item 1 of line CurrentLine of Source

    -- in case the line begins with a ":"
    if maybeTarget = EMPTY then
      set currentline = currentline - 1
    else if maybeTarget = Target then
      set found = TRUE
    else if (RangeEnd - RangeBegin = 1) then
      if item 1 of line RangeEnd of source = target then
        set found = TRUE
        set CurrentLine = rangeEnd
      else if item 1 of line RangeBegin of source = target then
        set found = TRUE
        set CurrentLine = RangeBegin
      else
        exit repeat
      end if
    else if (RangeEnd - RangeBegin = 1) then
      set CurrentLine = RangeEnd
    else if maybeTarget < Target then
      set RangeBegin = CurrentLine
      set CurrentLine = RangeBegin + integer ((RangeEnd - RangeBegin) / 2)
    else -- maybeTarget > Target
      set RangeEnd = CurrentLine
      set CurrentLine = RangeBegin + integer ((RangeEnd - RangeBegin) / 2)
    end if
  end repeat

  set the itemDelimiter = oldDelimiter
  if found then
    return CurrentLine
  else
    return 0
  end if
end